/*
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is ST_EXT-S_UIMAST.
 *
 * The Initial Developer of the Original Code is
 * University of Rome, Tor Vergata
 * Portions created by the Initial Developer are Copyright (C) 2009
 * the Initial Developer. All Rights Reserved.
 */

package it.uniroma2.art.uimast.impl.partial_order;

import java.util.*;

/**
 * A map whose keys are partially ordered. It cannot contain neither
 * <code>null</code> values nor duplicated keys (according to {@link Object#equals(Object)})
 * 
 * @author <a href="mailto:manuel.fiorelli@gmail.com">Manuel Fiorelli</a>
 * 
 * @param <Key>
 *            the keys type
 * @param <Value>
 *            the values type
 */
public class POMap<Key, Value> implements Iterable<Pair<Key, Value>> {
	/**
	 * Constructs a <code>POMap</code> object.
	 * 
	 * @param comparator
	 *            a comparator defining a partial order relation
	 */
	public POMap(Comparator<Key> comparator) {
		// Constructs an hash set to store the key-value pairs.
		// Duplicated keys aren't allowed.
		map = new HashMap<Key, Value>();

		// Stores the comparator.
		this.comparator = comparator;

		// Creates a sequence of keys sorted wrt the given comparator.
		keys = new ArrayList<Key>();
	}

	/**
	 * Adds a key-value pair.
	 * 
	 * @param key
	 *            the key
	 * @param value
	 *            the value
	 * @return <code>true</code> iff the pair was successfully added
	 */
	public boolean add(Key key, Value value) {
		// Checks for duplicated keys.
		if (map.containsKey(key))
			return false;

		// Avoid null values.
		if(value == null)
			throw new IllegalArgumentException("A " + getClass().getSimpleName() + " cannot hold null values");
		
		// Adds the new key-value pair.
		map.put(key, value);

		// Adds the new key before the last key which is less or equal to it.

		for (int i = keys.size() - 1; i >= 0; i--) {
			Key el = keys.get(i);
			if (comparator.less_equal(el, key)) {
				keys.add(i + 1, key);
				return true; // returns after the new key was added.
			}
		}

		/*
		 * Every comparable key is bigger than the new key, which must be added
		 * in front of the list.
		 */
		keys.add(0, key);

		return true; // returns
	}

	/**
	 * Removes a key-value pair.
	 * 
	 * @param key
	 *            the key
	 * @return the associated value or <code>null</code> if there isn't any
	 */
	public Value remove(Key key) {
		// Removes the key-value pair from the hash set.
		Value result = map.remove(key); // and gets the associated value.

		// Removes the key from the sorted list.
		for (Iterator<Key> it = keys.iterator(); it.hasNext();)
			if (it.next().equals(key)) {
				it.remove();
				break;
			}

		return result;
	}

	/**
	 * Iterates over the key-value pairs in this map. They are visited wrt to
	 * the partial order among their keys.
	 * 
	 * @return an iterator
	 */
	public Iterator<Pair<Key, Value>> iterator() {
		// Constructs an iterator.
		return new Iterator<Pair<Key, Value>>() {

			// Checks if there is another key-value pair.
			public boolean hasNext() {
				return orderedIt.hasNext();
			}

			// Gets the next pair.
			public Pair<Key, Value> next() {
				// Gets the current key
				Key key = orderedIt.next();

				// Constructs a pair with the associated value.
				return new Pair<Key, Value>(key, map.get(key));
			}

			// remove isn't supported.
			public void remove() {
				throw new UnsupportedOperationException(
						"Cannot remove an element from a POMap");
			}

			// an iterator over the ordered list of keys.
			private Iterator<Key> orderedIt = keys.iterator();
		};
	}

	/**
	 * Gets the value associated to a key.
	 * 
	 * @param key
	 *            the key
	 * @return the associated value, or <code>null</code> if there isn't any
	 */
	public Value get(Key key) {
		return map.get(key);
	}

	/**
	 * Checks if this map contains a given key.
	 * 
	 * @param key
	 *            the key
	 * @return <code>true</code> iff there is the given key
	 */
	public boolean containsKey(Object key) {
		return map.containsKey(key);
	}

	/**
	 * The hash set used to store the key-value pairs.
	 */
	private HashMap<Key, Value> map;

	/**
	 * A comparator which defined a partial order relation among the keys.
	 */
	private Comparator<Key> comparator;

	/**
	 * The list of keys sorted wrt the partial order relation defined by
	 * {@link #comparator}. It is used as an index to access the key-value pairs
	 * in order.
	 */
	private List<Key> keys;
}
